1. Field of Invention
The present invention relates generally to network systems. More particularly, the present invention relates to effectively reducing the average delay introduced by a store and forward buffer used for mixed-priority traffic.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Within an optical network, different networks, or environments, may be in communication with one another. For example, an overall network may include multiple environments which have different timing requirements. In order for packets to be sent between two environments with different timing requirements, buffers may be used between the environments to temporarily hold packets to effectively ensure that entire packets are moved into a receiving environment.
FIG. 1a is a diagrammatic representation of a network which includes a store and forward buffer that temporarily holds packets. A first environment 104, which is arranged to send packets from a network processor or a traffic management chip, is connected by a dedicated bus 106, e.g., a SPI3 bus or a SPI4 bus, to a store and forward buffer 116 that is typically associated with a framer or controller 112. As will be understood by those skilled in the art, a traffic management chip is a chip which provides buffering and queuing for packets. The size of buffer 116 is typically such that buffer 116 is at least one or two times the size of the maximum transmission unit that will be transmitted by first environment 104 or a second environment 108. Packets 120 which are sent from first environment 104 to buffer 116 are generally stored on buffer 116 until such time as buffer 116 may forward packets 120 on a bus 110 to second environment 108 on a first in, first out basis. Second environment 108 has an associated physical layer interface, as for example a synchronous optical network (SONET) interface, an Ethernet interface, or a T1/E1 interface. Second environment 108 typically has different timing requirements than first environment 104, so buffer 116 enables packet underrun to effectively be prevented by storing packets 120 until second environment 108 is ready to receive packets 120.
In many instances, packets 120 may be of mixed priorities. By way of example, first environment 104 may attempt to forward both low priority traffic and high priority traffic such as real-time traffic. When first environment 104 is providing packets 120 to buffer 116 faster than second environment 108 may receive them, i.e., when the exit rate from buffer 116 is insufficient to effectively support the entry rate into buffer 116, or when buffer 116 is nearly full, framer or controller 112 may send a per port backpressure 124 to first environment 104. In general, backpressure may either be sent over bus 106 or over separate lines (not shown). Backpressure 124 is effectively a jamming or a blocking technique which serves to enable frame losses to be reduced when one or more ports associated with framer or controller 112 are considered to be saturated. The use of backpressure 124 may prevent a deadlock situation between first environment 104 and framer or controller 112. As will be appreciated by those skilled in the art, when backpressure 124 is sent to first environment 104, first environment 104 may delay sending further packets 120 to buffer 116 until such time as it is appropriate to continue sending packets 120. A backpressure threshold which, when reached, causes a backpressure to be sent is restricted to being larger than a maximum packet size in order to avoid a deadlock condition. Restricting the backpressure threshold to be larger than the maximum packet size is needed to prevent a deadlock condition from being reached because the start of a packet transfer from buffer 116 to second environment 108 would not occur until an entire packet was received by buffer 116, but the receipt of the packet by buffer 116 would be stalled prior to completion until after packet transfer out of buffer 116 lowers the fill level of the buffer 116.
The relative packet transfer speed of first environment 104 will typically vary from the relative packet transfer speed of second environment 108. Either first environment 104 or second environment 108 may have a faster relative packet transfer speed. As such, buffer 116 must be designed to accommodate either condition, i.e., buffer 116 must be arranged to support first environment 104 having a higher relative packet transfer speed and second environment 108 having a higher relative packet transfer speed. When first environment 104 has a slower packet transfer speed than second environment 108, to prevent underrun of buffer 116, all of a packet must be buffered in buffer 116 before the packet begins to be sent to second environment 108. When first environment 104 has a faster packet transfer speed than second environment 108, to prevent overrun, backpressure is asserted from buffer 116 before buffer 116 is completely full, since buffer 116 must account for additional packet data sent before first environment 104 may fully respond to the backpressure request
When buffer 116 is full, e.g., full of low priority packets, when a high priority packet is to be sent by first environment 104 to second environment 108, there will generally be a delay before the high priority packet is received by second environment 108 since substantially all packets 120 already waiting in buffer 116 will need to be sent to second environment 108 before the high priority packet may reach second environment 108. The delay generally increases as the size of buffer 116 increases, and also as the speed associated with second environment 108 or, more specifically, a physical layer interface of second environment 108 decreases.
With reference to FIGS. 1b and 1c, the forwarding of a high priority packet through a substantially full store and forward buffer such as buffer 116 of FIG. 1a will be described. Buffer 116 contains low priority packets 120b-e which are to be forwarded out of buffer 116, e.g., after low priority packet 120a is forwarded out of buffer 116 and received by a receiving environment such as second environment 108 of FIG. 1a. A sorter 140 within first environment 104 sorts packets, as for example packets 120h-1, and substantially identifies high priority packets and low priority packets. As shown, since buffer 116 is relatively full, a high priority packet 120g is effectively queued to be sent to buffer 116 as soon as space is available in buffer 116, while a low priority packet 120f is effectively queued to be sent to buffer 116 after high priority packet 120g is sent.
Typically, high priority packets such as high priority packet 120g are expected to be transferred through buffer 116 with a low average latency, and low latency jitter. High priority packet 120g is delayed from reaching a receiving environment such as environment 108 of FIG. 1a because high priority packet 120g may not reach the receiving environment until substantially all packets which are already in buffer 116 reach the receiving environment. While high priority packet 120g may be forwarded to buffer 116 such that high priority packet 120g is queued in buffer 116 after low priority packet 120e, as shown in FIG. 1c, the delay between when high priority packet 120g is provided to buffer 116 and when high priority packet 120g is received by the receiving environment is essentially equal to the amount of time it takes to “drain” low priority packets 120b-e from buffer 116. For example, if buffer 116 is arranged to store approximately sixteen thousand bytes and is drained by a T1 line, the draining process may take approximately 85 milliseconds (ms), which may be an unacceptable delay for high priority packet 120g. 
As interface speeds increase, maximum packet size requirements and real-time traffic requirements also increase, thereby rendering the use of a single buffer to be ineffective. In addition, increased demands for systems which may accommodate a wide range of interface speeds further increase the difficulty of using a single buffer. In order to reduce the potential delays associated with sending high priority packets through a buffer which may be used for mixed-priority traffic, some framers or controllers may utilize two store and forward buffers, namely a store and forward buffer which is arranged to buffer low priority traffic and a store and forward buffer which is arranged to buffer high priority traffic FIG. 2a is a diagrammatic representation of a network that includes two store and forward buffers that are arranged to store packets. A first environment 204 is arranged to forward mixed priority traffic in the form of packets 220 to a second environment 208 through a framer or controller 212 which includes a first store and forward buffer 216a and a second store and forward buffer 216b. A dedicated bus 206 may be used to carry packets between first environment 204 and framer or controller 212, while a bus 210 may be used to carry packets between framer or controller 212 and second environment 208. Buffer 216a is arranged to effectively hold low priority packets received from first environment 204 until second environment 208 may receive the low priority packets, while buffer 216b is arranged to effectively hold high priority packets received from first environment 204 until second environment 208 may receive the high priority packet.
Framer or controller 212 may send a backpressure 224a which indicates that buffer 216a is full, and a backpressure 224b which indicates that buffer 216b is full. Hence, when buffer 216a is full, first environment 204 may continue to send high priority packets to buffer 216b, and when buffer 216b is full, first environment 204 may continue to send low priority packets to buffer 216a. 
The use of separate buffers 216a, 216b to hold low priority packets and high priority packets, respectively, may reduce delays associated with sending high priority packets to environment 208, as the need to effectively wait for low priority packets in a buffer, e.g., buffer 216a, to be drained before sending high priority packets may be substantially eliminated. Framer or controller 212 may be arranged to drain buffer 216a substantially only when buffer 216b has already been drained or is otherwise empty. As shown in FIG. 2b, a packet sorter or environment 204 may sort packets 220 and provide the sorted packets to buffers 216. When buffer 216b is empty, and buffer 216a contains low priority packets 220b-e, buffer 216a will forward low priority packets 220b-e to a receiving environment, as for example second environment 208 of FIG. 2a, after low priority packet 220a is received by the receiving environment.
When buffer 216b has any contents, as for example high priority packets 220h-k as shown in FIG. 2c, buffer 216b generally must effectively be drained before low priority packets 220b-e may be sent to a receiving environment. Further, substantially all high priority packets identified in first environment 204, e.g., high priority packet 2201, must also be sent to a receiving environment through buffer 216b before low priority packets 220b-e may be sent to the receiving environment. By way of example, high priority packets 220h-k, as well as high priority packet 2201 and other high priority packets currently identified in first environment 204, are sent to a receiving environment after high priority packet 220g before the first low priority packet in buffer 216a, namely low priority packet 220b, may be sent to the receiving environment. It should be understood that in some situations, the sending of packets 220 to a receiving environment may further be delayed when a backpressure is sent to first environment 204 to indicate that the transmission of packets between first environment 204 to buffers 216a, 216b should be slowed or delayed.
In general, the use of a separate high priority store and forward buffer in addition to a separate low priority store and forward buffer is effective for reducing the amount by which a high priority packet may be delayed or the latency associated with reaching a destination such as a receiving environment. The maximum latency and latency jitter associated with a high priority packet in a system which includes separate high priority and low priority store and forward buffers is not more than the time required to transfer a low priority packet that is in the process of being sent, i.e., no more than the amount of time required to transfer a large low priority packet to a receiving environment. In a best case, the latency would be approximately zero, so the maximum latency jitter is also relatively low. However, the use of two buffers to store and to forward mixed-priority traffic is both relatively expensive and relatively complex to implement, which may make the use of two buffers to reduce maximum latency and latency jitter inefficient and impractical.
Therefore, what is desired is a method and an apparatus for enabling potential delays associated with sending high priority packets in mixed-priority traffic to be efficiently reduced. More specifically, what is needed is a system which enables the number of packets stored in a store-and-forward buffer to be controlled such that the maximum amount by which a high priority packet may be delayed from reaching a destination may effectively be reduced.